package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.List;

public class Ti77 {
    private static List<List<Integer>> xx = new ArrayList<>();
    public static void main(String[] args) {
        long start = System.nanoTime();
        extracted();
        System.err.println((System.nanoTime() - start) / 1000/1000);
    }

    public void backtracking(int n, int k, int[] nums) {

    }

    /**
     * 没有剪枝
     */
    private static void extracted() {
        xx.clear();
        method(1, 30, 10, new ArrayList<>());
        System.err.println("OK");
    }

    private static void method(int start, int num, int count, List<Integer> res) {
        if (res.size() == count) {
            xx.add(new ArrayList<>(res));
            return;
        }
        // 第一次放一个数， 这次循环， 算是完事了
        // for (int i = start; i <= num; i++) {//没有剪枝
            for (int i = start; i <= (num - (count - res.size()) + 1); i++) {// 这个是带了剪枝操作的
            res.add(i);
            method(i+1, num, count, res);
            res.remove(res.size() - 1);
        }
    }


    public List<List<Integer>> combine(int n, int k) {
        xx.clear();
        m2(n, 0, k, new ArrayList<>());
        return xx;
    }

    private void m2(int n, int startIdex, int count, List<Integer> res) {
        if (res.size() == count) {
            xx.add(new ArrayList<>(res));
            return;
        }
        for (int i = startIdex; i <= (n - (count - res.size()) + 1); i++) {
            res.add(i);
            m2(n, i + 1, count, res);
            res.remove(res.size() - 1);
        }
    }
}
